import heapq
from typing import List


class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        intervals.append([10 ** 9, 10 ** 9])  # 添加哨兵任务

        ans = 0
        heap = []  # heap[i] = [任务最晚启动时间]

        for start, end in intervals:
            while heap and heap[0][0] + ans < start:
                if heap[0][0] + ans >= heap[0][1]:  # 任务已经被完成了
                    heapq.heappop(heap)
                else:
                    ans += min(heap[0][1], start) - heap[0][0] - ans  # 运行到当前时间或运行到任务结束
            heapq.heappush(heap, [end - 2 + 1 - ans, end + 1])  # 当前之前的运行时间是无效的，所以减去ans
        return ans


if __name__ == "__main__":
    # 3
    print(Solution().intersectionSizeTwo(intervals=[[1, 3], [1, 4], [2, 5], [3, 5]]))

    # 5
    print(Solution().intersectionSizeTwo(intervals=[[1, 2], [2, 3], [2, 4], [4, 5]]))
